package pers.qianyu.month_202103.date_20210309;

import java.util.*;

/**
 * 1047. 删除字符串中的所有相邻重复项
 * https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
 *
 * @author mizzle rain
 * @date 2021-03-09 11:22
 */
public class RemoveDuplicates {
    public String removeDuplicates(String S) {
        int n = S.length();
        if (n == 0) return S;
        char[] arr = S.toCharArray();
        Deque<Character> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (!st.isEmpty() && arr[i] == st.getLast()) {
                st.pollLast();
            } else {
                st.addLast(arr[i]);
            }
        }
        StringBuilder builder = new StringBuilder();
        while (!st.isEmpty()) {
            builder.append(st.pollFirst());
        }
        return builder.toString();
    }
}
